home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / dev / devQueue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  15.2 KB  |  453 lines
  1. /* 
  2.  * devQueue.c --
  3.  *
  4.  *    Routines to implement the DevQueue data type. 
  5.  *    Device queues define a queuing mechanism designed for implementing
  6.  *    queuing in low level device drivers.  The module interface provided is 
  7.  *    very simple.  Each controller in the system keeps one queue per
  8.  *    device attached to it. Requests are sent to a device by inserting 
  9.  *    the request into the queue for that device.  When a request becomes 
  10.  *    available in the queue for a device, the queue module notifies the
  11.  *    controller using a callback. The controller then has the option
  12.  *    of processing the request or informing the queue module to
  13.  *    enqueue it.  
  14.  *
  15.  * Copyright 1989 Regents of the University of California
  16.  * Permission to use, copy, modify, and distribute this
  17.  * software and its documentation for any purpose and without
  18.  * fee is hereby granted, provided that the above copyright
  19.  * notice appear in all copies.  The University of California
  20.  * makes no representations about the suitability of this
  21.  * software for any purpose.  It is provided "as is" without
  22.  * express or implied warranty.
  23.  */
  24.  
  25. #ifndef lint
  26. static char rcsid[] = "$Header: /cdrom/src/kernel/Cvsroot/kernel/dev/devQueue.c,v 9.2 91/08/19 13:41:14 jhh Exp $ SPRITE (Berkeley)";
  27. #endif /* not lint */
  28.  
  29. #include <sprite.h>
  30. #include <list.h>
  31. #include <bit.h>
  32. #include <devQueue.h>
  33. #include <proc.h>
  34. #include <sync.h>
  35. #include <stdlib.h>
  36. #include <bstring.h>
  37.  
  38. /*
  39.  *    Design rationale
  40.  *
  41.  *    A queue per device is desirable for higher level software because
  42.  *    it allows the software to view each device as an individual entity
  43.  *    regardless of how the device is attached to the system.
  44.  *    It also allows simple implementation of queue reordering (such as for 
  45.  *    minimizing disk seek time).  Unfortunately, a queue per device 
  46.  *    may be inappropriate for controllers that are single-threaded. 
  47.  *    Each controller would have to implement collapsing these multiple 
  48.  *    device queues into a single queue for the controller.
  49.  *    The device queue module handles this complexity
  50.  *    by allowing the controller to specify a set of queues to the
  51.  *    dequeue operation and the queue module will handle the fair
  52.  *    scheduling of these requests to the controller.
  53.  *    When the controller looks for the next request
  54.  *    to handle it can specify a bit mask indicating which queues it would
  55.  *    be willing to take entries for.    The queue module will return a request
  56.  *    from one of these queues using round-robin scheduling to decide which
  57.  *    queue the request comes from.
  58.  *
  59.  *    How to use device queues.
  60.  *
  61.  *    1) Each controller that wishes to maintain device queues should 
  62.  *       call Dev_CtrlQueuesCreate() to get a DevCtrlQueues on to
  63.  *       which the device queues can be added. An argument to this
  64.  *       call is the procedure to call when an entry becomes available on a
  65.  *       queue attached to the controller.
  66.  *    2) For each device attached to this controller, the driver should 
  67.  *       create a queue with the Dev_QueueCreate() call. The arguments
  68.  *       allow specification of the queue insert procedure (see below)
  69.  *       and the queue bit.  The queue bit must have at most one bit
  70.  *       set in it. Dev_QueueCreate() also lets the caller specify a
  71.  *       word of clientData passed to the controller's entryAvailProc when
  72.  *       an entry appears on the queue.
  73.  *    3) Once the queue is created, entries can be inserted with the
  74.  *       Dev_QueueInsert() routine.
  75.  *    4) To get the next entry off a queue the controller calls the
  76.  *       routine Dev_QueueGetNext(). The controller may also call
  77.  *       Dev_QueueGetNextFromSet() that takes the next entry from a 
  78.  *       set of queues represented in a bit mask.
  79.  *
  80.  *     Other features available in Device Queues:
  81.  *
  82.  *    1) Data structures are locked with MASTER_LOCKS() using the 
  83.  *       Sync_Semaphore specified by the controller. This allows the
  84.  *       QueueGetNext routines can be called at interrupt time.
  85.  *    2) The predefined insert "function" DEV_QUEUE_FIFO_INSERT can
  86.  *       be specified to the Dev_QueueCreate call to get first in
  87.  *       first out queuing.
  88.  *
  89.  * Data structures used to implement device queues.
  90.  *
  91.  * CtrlQueues - Contains per controller list of device queues.  This structure
  92.  * is returned by CtrlQueuesCreate and passed to QueueCreate to link
  93.  * device queues of a controller. It contains the lock for the queues and 
  94.  * information about ready queues.  When an entry is taken from a queue, 
  95.  * the queue is moved to the rear of the ready list.  This implements the 
  96.  * round-robin scheduling of combined queues.  
  97.  * 
  98.  */
  99.  
  100. typedef struct CtrlQueues {
  101.     Sync_Semaphore *mutexPtr;     /* Lock use to protect this data structures
  102.                  * and all device queues attached to this
  103.                  * structure. This is specified by the 
  104.                  * Controller when it creates the the
  105.                  * DevCtrlQueues structure. */
  106.     Boolean  (*entryAvailProc)();/* Procedure to call when an entry becomes
  107.                  * available in a queue. Its calling sequence
  108.                  * is defined in Dev_CtrlQueuesCreate. */
  109.     List_Links readyListHdr;    /* A list of device queues with entries in
  110.                  * them. This list is used to do the 
  111.                  * round-robin scheduling. */
  112. } CtrlQueues;
  113.  
  114. /*
  115.  * Queue - The data structure for a device queue.  This structure contains
  116.  * per queue information about a DevQueue.
  117.  */
  118.  
  119. typedef struct Queue {
  120.     List_Links    links;    /* Used to link the queue into ready and empty lists
  121.              * in the CtrlQueues structure. */
  122.     CtrlQueues    *ctrlPtr;   /* Controller for this device queue. */
  123.     ClientData    clientData; /* The ClientData to use on entryAvail callbacks
  124.                  * for this queue.   */
  125.     void   (*insertProc)(); /* Insert procedure to use from this queue. */
  126.     unsigned int  queueBit; /* Bit used to specify this queue to the
  127.                  * GetNextFromSet() routine. */
  128.     List_Links elementListHdr; /* List of elements on this queue. */
  129.  
  130. } Queue;
  131.  
  132. /*
  133.  *----------------------------------------------------------------------
  134.  *
  135.  *  Dev_CtrlQueuesCreate --
  136.  *
  137.  *    Allocate the data structures necessary to maintain queues for a
  138.  *    device controller with multiple devices.  Memory for the 
  139.  *    DevCtrlQueue data structure is malloc-ed and initialized.
  140.  *
  141.  * Results:
  142.  *    The DevCtrlQueue for this controller.
  143.  *
  144.  * Side effects:
  145.  *    Memory for the DevCtrlQueue data structure is malloc-ed and
  146.  *    initialized. The entryAvalProc may be called at a latter time
  147.  *    with the following arguments:
  148.  *
  149.  *    Boolean entryAvailProc(clientData, newRequestPtr)
  150.  *        ClientData clientData;    -- clientData specified for queue 
  151.  *                       this entry was for.
  152.  *        List_Links *newRequestPtr; -- New queue entry 
  153.  *    The entryAvailProc should return TRUE if the newRequest was
  154.  *    processed. If the FALSE is return the queue module will enqeue
  155.  *    the newRequest.
  156.  *
  157.  *----------------------------------------------------------------------
  158.  */
  159.  
  160. DevCtrlQueues
  161. Dev_CtrlQueuesCreate(mutexPtr, entryAvailProc)
  162.     Sync_Semaphore *mutexPtr;    /* Semaphore used to protect this data 
  163.                  * structure. */
  164.     Boolean (*entryAvailProc)();/* Procedure to call when a queue for a device
  165.                  * on this controller moves from empty to
  166.                  * having an entry present. */
  167. {
  168.     CtrlQueues     *ctrlPtr;
  169.  
  170.     ctrlPtr = (CtrlQueues *) malloc(sizeof(CtrlQueues));
  171.     bzero((char *) ctrlPtr, sizeof(CtrlQueues));
  172.     /*
  173.      * Initialize the lock used to protect queues under the control
  174.      * of this controller.
  175.      */
  176.     ctrlPtr->mutexPtr = mutexPtr;
  177.     /*
  178.      * Initialize the envtyAvailProc and the ready mask.
  179.      */
  180.     ctrlPtr->entryAvailProc = entryAvailProc;
  181.     /*
  182.      * Initialize the list headers for the ready list for
  183.      * the device queues attached to this controller.
  184.      */
  185.     List_Init(&(ctrlPtr->readyListHdr));
  186.     return (DevCtrlQueues) ctrlPtr;
  187. }
  188.  
  189.  
  190. /*
  191.  *----------------------------------------------------------------------
  192.  *
  193.  * Dev_QueueCreate --
  194.  *
  195.  *    Allocate and initialize the data structures for a device queue.
  196.  *    The queue will come up empty. The queueBit is used to group the 
  197.  *    newly created queue with the other queues using the same queueBit bit.
  198.  *
  199.  * Results:
  200.  *    The allocated DevQueue structure.
  201.  *
  202.  * Side effects:
  203.  *    Memory allocated and the newly created queue is added to the 
  204.  *    empty queue list of the controller. The insertProc procedure
  205.  *    may be called when elements become available.
  206.  *    The queue insert routine is responsible
  207.  *    for inserting the new entry in the linked list for the device. The
  208.  *    entries in the list are given to the device in the list order.
  209.  *     It should be declared:
  210.  *
  211.  *    void insertProc(elementPtr,listHeaderPtr)
  212.  *        List_Links  *elementPtr;    -- Element to add.
  213.  *        List_Links  *listHeaderPtr; -- Header of list to add to.
  214.  *
  215.  *    See the List man page for a description on how list work.
  216.  *
  217.  *----------------------------------------------------------------------
  218.  */
  219.  
  220. DevQueue
  221. Dev_QueueCreate(ctrlQueue, queueBit, insertProc, clientData)
  222.     DevCtrlQueues ctrlQueue;    /* Pointer to the controller to which this
  223.                  * queue belongs. Must be a pointer returned
  224.                  * from Dev_CtrlQueuesCreate.*/
  225.     void (*insertProc)();    /* Queue insert routine.  */
  226.     unsigned int queueBit;    /* Bit value used to identify queue in 
  227.                  * select mask for the GetNextFromSet() call. 
  228.                  * Only zero or one bit should be set in this
  229.                  * integer.  A zero value means the queue
  230.                  * is not in a set. */
  231.     ClientData    clientData;    /* Field passed to the entryAvailProc for the
  232.                  * controller when an entry because available
  233.                  * in this DevQueue. */
  234. {
  235.     CtrlQueues     *ctrlPtr = (CtrlQueues *) ctrlQueue;
  236.     Queue     *queuePtr;
  237.     /*
  238.      * Allocated and initialize the DevQueue structure for this queue. 
  239.      */
  240.     queuePtr = (Queue *) malloc(sizeof(Queue));
  241.     bzero((char *)queuePtr, sizeof(Queue));
  242.     queuePtr->ctrlPtr = ctrlPtr;
  243.     queuePtr->clientData = clientData;
  244.     queuePtr->insertProc = insertProc;
  245.     queuePtr->queueBit = queueBit;
  246.     List_Init(&(queuePtr->elementListHdr));
  247.     return (DevQueue) queuePtr;
  248.  
  249. }
  250.  
  251. /*
  252.  *----------------------------------------------------------------------
  253.  *
  254.  * Dev_QueueDestroy --
  255.  *
  256.  *    Release the resources held by a queue.
  257.  *
  258.  * Results:
  259.  *    TRUE if the queue is was destroyed. FALSE if the queue could not
  260.  *     be freed because it was not empty.
  261.  *
  262.  * Side effects:
  263.  *    Memory may be free'ed.
  264.  *
  265.  *----------------------------------------------------------------------
  266.  */
  267.  
  268. Boolean
  269. Dev_QueueDestroy(devQueue)
  270.     DevQueue    devQueue;    /* Queue to destory. */
  271. {
  272.     Queue     *queuePtr = (Queue *) devQueue;
  273.  
  274.     /*
  275.      * Don't try to delete empty queue.
  276.      */
  277.     if (!List_IsEmpty(&(queuePtr->elementListHdr))) {
  278.     return FALSE;
  279.     }
  280.     /*
  281.      * Release the lock on the queue entry.  There is an inherent race 
  282.      * condition with the freeing of a queue if someone else is still
  283.      * trying to add entries to the queue. The user of the queue must 
  284.      * make sure this doesn't happen.
  285.      *
  286.      */
  287.     free((char *) queuePtr);
  288.     return TRUE;
  289. }
  290.  
  291.  
  292. /*
  293.  *----------------------------------------------------------------------
  294.  *
  295.  * Dev_QueueInsert --
  296.  *    
  297.  *    Insert an entry into the specified device queue.  If the device
  298.  *    queue is not on the ready list it is added to the ready list.
  299.  *
  300.  * Results:
  301.  *    None.
  302.  *
  303.  * Side effects:
  304.  *    The queue controller's entryAvailProc maybe called. The queue may
  305.  *    be moved from the controller's emptyList to the readyList of its
  306.  *    combine tag.
  307.  *
  308.  *----------------------------------------------------------------------
  309.  */
  310.  
  311. void
  312. Dev_QueueInsert(devQueue, elementPtr)
  313.     DevQueue    devQueue;    /* Queue to insert into. */
  314.     List_Links  *elementPtr;    /* Entry to insert. */
  315. {
  316.     register Queue     *queuePtr = (Queue *) devQueue;
  317.     register CtrlQueues  *ctrlPtr = queuePtr->ctrlPtr;
  318.     register Boolean     wasEmpty;
  319.  
  320.     MASTER_LOCK(ctrlPtr->mutexPtr);
  321.     wasEmpty = List_IsEmpty(&(queuePtr->elementListHdr));
  322.     /*
  323.      * Insert the elment in the queue's list of elements if the entry
  324.      * avail procedure doesn't take it.
  325.      */
  326.     if (wasEmpty) {
  327.     Boolean    taken;
  328.     taken = (ctrlPtr->entryAvailProc)(queuePtr->clientData,elementPtr);
  329.     if (taken) {
  330.         MASTER_UNLOCK(ctrlPtr->mutexPtr);
  331.         return;
  332.     }
  333.     }
  334.     if (queuePtr->insertProc != DEV_QUEUE_FIFO_INSERT) { 
  335.     (queuePtr->insertProc)(elementPtr,&(queuePtr->elementListHdr));
  336.     } else {
  337.     List_Insert(elementPtr, LIST_ATREAR(&(queuePtr->elementListHdr)));
  338.     }
  339.     /*
  340.      * If the queue moved from empty to available, move this queue 
  341.      * to the ready list.  This need only be done if the queue is in
  342.      * a set.
  343.      */
  344.     if (wasEmpty && (queuePtr->queueBit != 0)) {
  345.     register List_Links *readyList;
  346.     readyList = &(ctrlPtr->readyListHdr);
  347.     wasEmpty = List_IsEmpty(readyList);
  348.     List_Insert((List_Links *) queuePtr, LIST_ATREAR(readyList));
  349.     }
  350.     MASTER_UNLOCK(ctrlPtr->mutexPtr);
  351. }
  352.  
  353.  
  354. /*
  355.  *----------------------------------------------------------------------
  356.  *
  357.  * Dev_QueueGetNext --
  358.  *    
  359.  *    Remove the element from a device queue.
  360.  *
  361.  *    NOTE: This routine assumes that the caller as the ctrlPtr->mutexPtr
  362.  *    held.
  363.  *
  364.  * Results:
  365.  *    The element removed.  NIL if queue was empty.
  366.  *
  367.  * Side effects:
  368.  *    Entry removed from a queue and the queue may be moved from the
  369.  *    ready list to empty list.
  370.  *----------------------------------------------------------------------
  371.  */
  372.  
  373. List_Links  *
  374. Dev_QueueGetNext(devQueue)
  375.     DevQueue    devQueue;        /* Queue remove element from. */
  376. {
  377.     register Queue     *queuePtr = (Queue *) devQueue;
  378.     register CtrlQueues  *ctrlPtr = queuePtr->ctrlPtr;
  379.     List_Links    *returnValue;
  380.  
  381.     /*
  382.      * If the queue is empty just return.
  383.      */
  384.     if (List_IsEmpty(&(queuePtr->elementListHdr))) {
  385.     return (List_Links *) NIL;
  386.     } 
  387.     /*
  388.      * Take the first entry of the queue. If the queue is now empty 
  389.      * remove it from the readyList. Otherwise move it to the end 
  390.      * of the ready list to implement round-robining in the
  391.      * Dev_QueueGetNextFromSet routine. 
  392.      */
  393.     returnValue = List_First(&(queuePtr->elementListHdr));
  394.     List_Remove(returnValue);
  395.     if (queuePtr->queueBit != 0) {
  396.     if (List_IsEmpty(&(queuePtr->elementListHdr))) {
  397.         List_Remove((List_Links *) queuePtr);
  398.      } else {
  399.         List_Move((List_Links *) queuePtr, 
  400.             LIST_ATREAR(&(ctrlPtr->readyListHdr)));
  401.     }
  402.     }
  403.     return returnValue;
  404.  
  405. }
  406.  
  407. /*
  408.  *----------------------------------------------------------------------
  409.  *
  410.  * Dev_QueueGetNextFromSet --
  411.  *    
  412.  *    Remove next the element from a set of queues using LRU scheduling.
  413.  *
  414.  *    NOTE: This routine assumes that the caller as the ctrlPtr->mutexPtr
  415.  *    held.
  416.  *
  417.  * Results:
  418.  *    The element removed.  NIL if all queues in the mask were empty.
  419.  *
  420.  * Side effects:
  421.  *    Entry removed from a queue and the queue may be moved from the
  422.  *    ready list to empty list.
  423.  *----------------------------------------------------------------------
  424.  */
  425.  
  426. List_Links  *
  427. Dev_QueueGetNextFromSet(ctrl, queueMask, clientDataPtr)
  428.     DevCtrlQueues ctrl;        /* Controller to examine queues of. */
  429.     unsigned int queueMask;        /* Mask of queues to examine. */
  430.     ClientData    *clientDataPtr;        /* Filled in the with clientdata
  431.                      * for the queue of the entry 
  432.                      * returned. */
  433. {
  434.     register Queue     *queuePtr;
  435.     register List_Links *itemPtr;
  436.     CtrlQueues  *ctrlPtr = (CtrlQueues *) ctrl;
  437.  
  438.     /*
  439.      * Scan down the ready list for the first queue that has the queue bit 
  440.      * set in the mask.
  441.      */
  442.     LIST_FORALL(&(ctrlPtr->readyListHdr), itemPtr) {
  443.     queuePtr = (Queue *) itemPtr;
  444.     if (queueMask & (queuePtr->queueBit)) {
  445.         *clientDataPtr = queuePtr->clientData;
  446.         return Dev_QueueGetNext((DevQueue) queuePtr);
  447.     }
  448.     }
  449.     return (List_Links *) NIL;
  450. }
  451.  
  452.  
  453.